package com.xie.leetcode.math;

/**
 * @author xiezhendong
 * @date 2021/11/19
 */
public class IntegerReplacement {

    public static void main(String[] args) {
        IntegerReplacement integerReplacement = new IntegerReplacement();
        System.out.println(integerReplacement.integerReplacement(8));
        System.out.println(integerReplacement.integerReplacement(7));
        System.out.println(integerReplacement.integerReplacement(4));
    }

    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + integerReplacement(n / 2);
        } else {
            return 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
        }
    }
}
